package leetcode.slidwidow;

import java.util.HashSet;

public class Lc76 {

    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        String ans = null;
        int[] cnt = new int['z' - 'A' + 1];
        HashSet<Character> tSet = new HashSet<>();
        for (int i = 0; i < t.length(); i++) {
            cnt[t.charAt(i) - 'A']++;
            tSet.add(t.charAt(i));
        }
        int sum = t.length();
        for (int i = 0, j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            if (tSet.contains(c)) {
                if (cnt[c - 'A'] > 0) sum--;
                cnt[c - 'A']--;
                if (sum == 0) {
                    c = s.charAt(i);
                    while (sum == 0 && (!tSet.contains(c) || cnt[c - 'A'] <= 0)) {
                        if (ans == null || ans.length() > j - i + 1) {
                            ans = s.substring(i, j + 1);
                        }
                        if (tSet.contains(c)) {
                            cnt[c - 'A']++;
                            if (cnt[c - 'A'] > 0) sum++;
                        }
                        i++;
                        if (i > j) break;
                        c = s.charAt(i);
                    }
                }
            }
        }
        return ans == null ? "" : ans;
    }


    public static void main(String[] args) {
        Lc76 lc76 = new Lc76();
        System.out.println(lc76.minWindow("gehzduwqkzuyotckqcusdiqubeqglkvuocttzrllqfjhzorpqnjwxbqyfiesscmigicfzn", "qsvczwsslkhwg"));
//        int x1 = 'a';
//        int x2 = 'z';
//        int x3 = 'A';
//        int x4 = 'Z';
//
//
//        System.out.println(x1);
//        System.out.println(x2);
//        System.out.println(x3);
        System.out.println('z' - 'A');
        System.out.println('a' - 'A');
    }













}
